package com.ljy.my_study.leetcode.分隔链表;

import com.ljy.my_study.util.ListNodeUtil;
import com.ljy.my_study.util.ListNodeUtil.*;

/**
 * @author lijunying
 * @date 2021/11/12 16:35
 */
public class TestMain {

//    给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//
//    你应当 保留 两个分区中每个节点的初始相对位置。
//
//             
//
//    示例 1：
//
//
//    输入：head = [1,4,3,2,5,2], x = 3
//    输出：[1,2,2,4,3,5]
//    示例 2：
//
//    输入：head = [2,1], x = 2
//    输出：[1,2]
//             
//
//    提示：
//
//    链表中节点的数目在范围 [0, 200] 内
//-100 <= Node.val <= 100
//            -200 <= x <= 200
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/partition-list
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        ListNode head=ListNodeUtil.createListNode(new int[]{1,3,4,4,3,2,1,4,1});
        int x=3;
        System.out.println(new TestMain().partition(head,x));
    }

    public ListNode partition(ListNode head, int x) {
        ListNode node=new ListNode(x-1,head);
        head=node;
        ListNode preNode=null;
        ListNode changeNode=null;
        while(node!=null){
            ListNode next=node.next;
            if(next==null){
                break;
            }
            if(next.val>=x&&changeNode==null){
                preNode=node;
                changeNode=next;
            }
            if(next.val<x&&preNode!=null){
                ListNode nextNext=next.next;
                next.next=null;
                node.next=nextNext;
                ListNode preNodeNext=preNode.next;
                preNode.next=next;
                next.next=preNodeNext;
                preNode=preNode.next;
                continue;
            }
            node=node.next;
        }
        return head.next;
    }
}
